home *** CD-ROM | disk | FTP | other *** search
/ Cobra Utilities for Doom & Doom II / Cobra Utilities For Doom & Doom II - Disc 2.iso / files / program / bsp12x / picknode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-14  |  6.4 KB  |  195 lines
  1. /*- PICKNODE.C --------------------------------------------------------------*
  2.  To be able to divide the nodes down, this routine must decide which is the
  3.  best Seg to use as a nodeline. It does this by selecting the line with least
  4.  splits and has least difference of Segs on either side of it.
  5.  
  6.  Credit to Raphael Quinet and DEU, this routine is a copy of the nodeline
  7.  picker used in DEU5beta. I am using this method because the method I 
  8.  originally used was not so good.
  9. *---------------------------------------------------------------------------*/
  10.  
  11. struct Seg *PickNode(struct Seg *ts)
  12. {
  13.     int num_splits,num_left,num_right;
  14.     int min_splits,min_diff,val;
  15.     struct Seg *part,*check,*best;
  16.     int max,new,grade = 0,bestgrade = 32767,seg_count;
  17.  
  18.    min_splits = 32767;
  19.    min_diff = 32767;
  20.    best = ts;                                    /* Set best to first (failsafe measure)*/
  21.  
  22.     for(part=ts;part;part = part->next)    /* Use each Seg as partition*/
  23.         {
  24.         progress();                                /* Something for the user to look at.*/
  25.         
  26.         psx = vertices[part->start].x;    /* Calculate this here, cos it doesn't*/
  27.         psy = vertices[part->start].y;    /* change for all the interations of*/
  28.         pex = vertices[part->end].x;        /* the inner loop!*/
  29.         pey = vertices[part->end].y;
  30.         pdx = psx - pex;                        /* Partition line DX,DY*/
  31.         pdy = psy - pey;
  32.     
  33.         num_splits = 0;
  34.         num_left = 0;
  35.         num_right = 0;
  36.  
  37.         seg_count = 0;
  38.         for(check=ts;check;check=check->next)    /* Check partition against all Segs*/
  39.             {
  40.             seg_count++;
  41.             if(check == part) num_right++;        /* If same as partition, inc right count*/
  42.             else
  43.                 {
  44.                 lsx = vertices[check->start].x;    /* Calculate this here, cos it doesn't*/
  45.                 lsy = vertices[check->start].y;    /* change for all the interations of*/
  46.                 lex = vertices[check->end].x;        /* the inner loop!*/
  47.                 ley = vertices[check->end].y;
  48.                 val = DoLinesIntersect();            /* get state of lines relation to each other*/
  49.                 if((val&2 && val&64) || (val&4 && val&32))
  50.                     {
  51.                     num_splits++;                        /* If line is split, inc splits*/
  52.                     num_left++;                            /* and add one line into both*/
  53.                     num_right++;                        /* sides*/
  54.                     }
  55.                 else
  56.                     {
  57.                     if(val&1 && val&16)                /* If line is totally in same*/
  58.                         {                                    /* direction*/
  59.                         if(check->flip == part->flip) num_right++;
  60.                         else num_left++;                /* add to side according to flip*/
  61.                         }
  62.                     else                                    /* So, now decide which side*/
  63.                         {                                    /* the line is on*/
  64.                         if(val&34) num_left++;        /* and inc the appropriate*/
  65.                         if(val&68) num_right++;        /* count*/
  66.                         }
  67.                     }
  68.                 }
  69. /*            if(num_splits > min_splits) break;    /* If more splits than last, reject*/
  70.             }
  71.  
  72.         if(num_right > 0 && num_left > 0)        /* Make sure at least one Seg is*/
  73.             {                                                /* on either side of the partition*/
  74.             max = max(num_right,num_left);
  75.             new = (num_right + num_left) - seg_count;
  76.             grade = max+new*8;
  77.  
  78.             if(grade < bestgrade)
  79.                 {
  80.                 bestgrade = grade;
  81.                 best = part;                            /* and remember which Seg*/
  82.                 }
  83.             }
  84.         }
  85.     return best;                                        /* all finished, return best Seg*/
  86. }
  87.  
  88. /*---------------------------------------------------------------------------*
  89.  Because this is used a horrendous amount of times in the inner loops, the
  90.  coordinate of the lines are setup outside of the routine in global variables
  91.  psx,psy,pex,pey = partition line coordinates
  92.  lsx,lsy,lex,ley = checking line coordinates
  93.  The routine returns 'val' which has 3 bits assigned to the the start and 3
  94.  to the end. These allow a decent evaluation of the lines state.
  95.  bit 0,1,2 = checking lines starting point and bits 4,5,6 = end point
  96.  these bits mean     0,4 = point is on the same line
  97.                          1,5 = point is to the left of the line
  98.                         2,6 = point is to the right of the line
  99.  There are some failsafes in here, these mainly check for small errors in the
  100.  side checker.
  101. *---------------------------------------------------------------------------*/
  102.  
  103. int DoLinesIntersect()
  104. {
  105.     short int x,y,val = 0;
  106.  
  107.     long dx2,dy2,dx3,dy3,a,b,l;
  108.     
  109.     dx2 = psx - lsx;                                    /* Checking line -> partition*/
  110.     dy2 = psy - lsy;
  111.     dx3 = psx - lex;
  112.     dy3 = psy - ley;
  113.     
  114.     a = pdy*dx2 - pdx*dy2;
  115.     b = pdy*dx3 - pdx*dy3;
  116.  
  117.     if((a<0 && b>0) || (a>0 && b<0))                /* Line is split, just check that*/
  118.         {
  119.         ComputeIntersection(&x,&y);
  120.         dx2 = lsx - x;                                    /* Find distance from line start*/
  121.         dy2 = lsy - y;                                    /* to split point*/
  122.         if(dx2 == 0 && dy2 == 0) a = 0;
  123.         else
  124.             {
  125.             l = (long)sqrt((float)((dx2*dx2)+(dy2*dy2)));        /* If either ends of the split*/
  126.             if(l < 2) a = 0;                            /* are smaller than 2 pixs then*/
  127.             }                                                /* assume this starts on part line*/
  128.         dx3 = lex - x;                                    /* Find distance from line end*/
  129.         dy3 = ley - y;                                    /* to split point*/
  130.         if(dx3 == 0 && dy3 == 0) b = 0;
  131.         else
  132.             {
  133.             l = (long)sqrt((float)((dx3*dx3)+(dy3*dy3)));        /* same as start of line*/
  134.             if(l < 2) b = 0;
  135.             }
  136.         }
  137.  
  138.     if(a == 0) val = val | 16;                        /* start is on middle*/
  139.     if(a < 0) val = val | 32;                        /* start is on left side*/
  140.     if(a > 0) val = val | 64;                        /* start is on right side*/
  141.  
  142.     if(b == 0) val = val | 1;                        /* end is on middle*/
  143.     if(b < 0) val = val | 2;                        /* end is on left side*/
  144.     if(b > 0) val = val | 4;                        /* end is on right side*/
  145.  
  146.     return val;
  147. }
  148.  
  149. /*---------------------------------------------------------------------------*
  150.  Calculate the point of intersection of two lines. ps?->pe? & ls?->le?
  151.  returns int xcoord, int ycoord
  152. *---------------------------------------------------------------------------*/
  153.  
  154. void ComputeIntersection(short int *outx,short int *outy)
  155. {
  156.     double a,b,a2,b2,l,l2,w,d,z;
  157.     
  158.     long dx,dy,dx2,dy2;
  159.  
  160.     dx = pex - psx;
  161.     dy = pey - psy;
  162.     dx2 = lex - lsx;
  163.     dy2 = ley - lsy;
  164.  
  165.     if(dx == 0 && dy == 0) ProgError("Trouble in ComputeIntersection dx,dy");
  166.     l = (long)sqrt((float)((dx*dx) + (dy*dy)));
  167.     if(dx2 == 0 && dy2 == 0) ProgError("Trouble in ComputeIntersection dx2,dy2");
  168.     l2 = (long)sqrt((float)((dx2*dx2) + (dy2*dy2)));
  169.     
  170.     a = dx / l;
  171.     b = dy / l;
  172.     a2 = dx2 / l2;
  173.     b2 = dy2 / l2;
  174.     d = b * a2 - a * b2;
  175.     w = lsx;
  176.     z = lsy;
  177.     if(d != 0.0)
  178.         {
  179.         w = (((a*(lsy-psy))+(b*(psx-lsx))) / d);
  180.     
  181. /*        printf("Intersection at (%f,%f)\n",x2+(a2*w),y2+(b2*w));*/
  182.     
  183.         a = lsx+(a2*w);
  184.         b = lsy+(b2*w);
  185.         modf((float)(a)+ ((a<0)?-0.5:0.5) ,&w);
  186.         modf((float)(b)+ ((b<0)?-0.5:0.5) ,&z);
  187.         }
  188.     
  189.     *outx = w;
  190.     *outy = z;
  191. }
  192.  
  193. /*--------------------------------------------------------------------------*/
  194.  
  195.